Feistel Network
   HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s, named after the
German German(s) may refer to: * Germany (of or related to) ** Germania (historical use) * Germans, citizens of Germany, people of German ancestry, or native speakers of the German language ** For citizens of Germany, see also German nationality law **Ge ...
-born
physicist A physicist is a scientist who specializes in the field of physics, which encompasses the interactions of matter and energy at all length and time scales in the physical universe. Physicists generally are interested in the root or ultimate caus ...
and cryptographer
Horst Feistel Horst Feistel (January 30, 1915 – November 14, 1990) was a German-American cryptographer who worked on the design of ciphers at IBM, initiating research that culminated in the development of the Data Encryption Standard (DES) in the 1970s. The ...
, who did pioneering research while working for IBM; it is also commonly known as a Feistel network. A large proportion of
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s use the scheme, including the US
Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cry ...
, the Soviet/Russian
GOST GOST (russian: ГОСТ) refers to a set of International standard, international Technical standard, technical Standardization, standards maintained by the ''Euro-Asian Council for Standardization, Metrology and Certification (EASC)'', a region ...
and the more recent
Blowfish Tetraodontidae is a family of primarily marine and estuarine fish of the order Tetraodontiformes. The family includes many familiar species variously called pufferfish, puffers, balloonfish, blowfish, blowies, bubblefish, globefish, swellfis ...
and
Twofish In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Twof ...
ciphers. In a Feistel cipher, encryption and decryption are very similar operations, and both consist of iteratively running a function called a "round function" a fixed number of times.


History

Many modern symmetric block ciphers are based on Feistel networks. Feistel networks were first seen commercially in IBM's
Lucifer Lucifer is one of various figures in folklore associated with the planet Venus. The entity's name was subsequently absorbed into Christianity as a name for the devil. Modern scholarship generally translates the term in the relevant Bible passage ...
cipher, designed by
Horst Feistel Horst Feistel (January 30, 1915 – November 14, 1990) was a German-American cryptographer who worked on the design of ciphers at IBM, initiating research that culminated in the development of the Data Encryption Standard (DES) in the 1970s. The ...
and
Don Coppersmith Don Coppersmith (born 1950) is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S-boxes, strengthening them against differential cryptanalysis ...
in 1973. Feistel networks gained respectability when the U.S. Federal Government adopted the
DES Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...
(a cipher based on Lucifer, with changes made by the
NSA The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
) in 1976. Like other components of the DES, the iterative nature of the Feistel construction makes implementing the cryptosystem in hardware easier (particularly on the hardware available at the time of DES's design).


Design

A Feistel network uses a ''round function'', a function which takes two inputs a data block and a subkey and returns one output of the same size as the data block. In each round, the round function is run on half of the data to be encrypted, and its output is XORed with the other half of the data. This is repeated a fixed number of times, and the final output is the encrypted data. An important advantage of Feistel networks compared to other cipher designs such as substitution–permutation networks is that the entire operation is guaranteed to be invertible (that is, encrypted data can be decrypted), even if the round function is not itself invertible. The round function can be made arbitrarily complicated, since it does not need to be designed to be invertible. Furthermore, the
encryption In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
and
decryption In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
operations are very similar, even identical in some cases, requiring only a reversal of the
key schedule In cryptography, the so-called product ciphers are a certain kind of cipher, where the (de-)ciphering of data is typically done as an iteration of ''rounds''. The setup for each round is generally the same, except for round-specific fixed valu ...
. Therefore, the size of the code or circuitry required to implement such a cipher is nearly halved.


Theoretical work

The structure and properties of Feistel ciphers have been extensively analyzed by
cryptographer Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
s.
Michael Luby Michael George Luby is a mathematician and computer scientist, CEO of BitRipple, Senior Research Scientist at the International Computer Science Institute (ICSI), former VP Technology at Qualcomm, co-founder and former Chief Technology Office ...
and
Charles Rackoff Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, he attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar ...
analyzed the Feistel cipher construction and proved that if the round function is a cryptographically secure
pseudorandom function In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) betwee ...
, with ''Ki'' used as the seed, then 3 rounds are sufficient to make the block cipher a pseudorandom permutation, while 4 rounds are sufficient to make it a "strong" pseudorandom permutation (which means that it remains pseudorandom even to an adversary who gets
oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The word '' ...
access to its inverse permutation).. Because of this very important result of Luby and Rackoff, Feistel ciphers are sometimes called Luby–Rackoff block ciphers. Further theoretical work has generalized the construction somewhat and given more precise bounds for security.


Construction details

Let \mathrm be the round function and let K_0, K_1, \ldots, K_n be the sub-keys for the rounds 0, 1, \ldots, n respectively. Then the basic operation is as follows: Split the plaintext block into two equal pieces: (L_0, R_0). For each round i = 0, 1, \dots, n, compute : L_ = R_i, : R_= L_i \oplus \mathrm(R_i, K_i), where \oplus means XOR. Then the ciphertext is (R_, L_). Decryption of a ciphertext (R_, L_) is accomplished by computing for i = n, n - 1, \ldots, 0 : R_ = L_, : L_ = R_ \oplus \operatorname(L_, K_i). Then (L_0, R_0) is the plaintext again. The diagram illustrates both encryption and decryption. Note the reversal of the subkey order for decryption; this is the only difference between encryption and decryption.


Unbalanced Feistel cipher

Unbalanced Feistel ciphers use a modified structure where L_0 and R_0 are not of equal lengths. The Skipjack cipher is an example of such a cipher. The
Texas Instruments Texas Instruments Incorporated (TI) is an American technology company headquartered in Dallas, Texas, that designs and manufactures semiconductors and various integrated circuits, which it sells to electronics designers and manufacturers globall ...
digital signature transponder uses a proprietary unbalanced Feistel cipher to perform
challenge–response authentication In computer security, challenge–response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to be authenticated. The simplest example of a ch ...
. The
Thorp shuffle ''Thorp'' is a Middle English word for a hamlet or small village. Etymology The name can either come from Old Norse ''þorp'' (also ''thorp''), or from Old English (Anglo-Saxon) ''þrop''. There are many place names in England with the suff ...
is an extreme case of an unbalanced Feistel cipher in which one side is a single bit. This has better provable security than a balanced Feistel cipher but requires more rounds.


Other uses

The Feistel construction is also used in cryptographic algorithms other than block ciphers. For example, the optimal asymmetric encryption padding (OAEP) scheme uses a simple Feistel network to randomize ciphertexts in certain asymmetric-key encryption schemes. A generalized Feistel algorithm can be used to create strong permutations on small domains of size not a power of two (see
format-preserving encryption In cryptography, format-preserving encryption (FPE), refers to encrypting in such a way that the output (the ciphertext) is in the same format as the input (the plaintext). The meaning of "format" varies. Typically only finite sets of characters ar ...
).


Feistel networks as a design component

Whether the entire cipher is a Feistel cipher or not, Feistel-like networks can be used as a component of a cipher's design. For example,
MISTY1 In cryptography, MISTY1 (or MISTY-1) is a block cipher designed in 1995 by Mitsuru Matsui and others for Mitsubishi Electric. MISTY1 is one of the selected algorithms in the European NESSIE project, and has been among the cryptographic tech ...
is a Feistel cipher using a three-round Feistel network in its round function, Skipjack is a modified Feistel cipher using a Feistel network in its G permutation, and
Threefish Threefish is a symmetric-key tweakable block cipher designed as part of the Skein hash function, an entry in the NIST hash function competition. Threefish uses no S-boxes or other table lookups in order to avoid cache timing attacks; The paper ...
(part of
Skein Skein may refer to: * A flock of geese or ducks in flight * A wound ball of yarn with a centre pull strand; see Hank * A metal piece fitted over the end of a wagon axle, to which the wheel is mounted * Skein (unit), a unit of length used by wea ...
) is a non-Feistel block cipher that uses a Feistel-like MIX function.


List of Feistel ciphers

Feistel or modified Feistel: *
Blowfish Tetraodontidae is a family of primarily marine and estuarine fish of the order Tetraodontiformes. The family includes many familiar species variously called pufferfish, puffers, balloonfish, blowfish, blowies, bubblefish, globefish, swellfis ...
*
Camellia ''Camellia'' (pronounced or ) is a genus of flowering plants in the family Theaceae. They are found in eastern and southern Asia, from the Himalayas east to Japan and Indonesia. There are more than 220 described species, with some controversy ...
*
CAST-128 In cryptography, CAST-128 (alternatively CAST5) is a symmetric-key block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has also been approved for Government of Canada use by the Communic ...
*
DES Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...
*
FEAL In cryptography, FEAL (the Fast data Encipherment ALgorithm) is a block cipher proposed as an alternative to the Data Encryption Standard (DES), and designed to be much faster in software. The Feistel based algorithm was first published in 1987 ...
* GOST 28147-89 *
ICE Ice is water frozen into a solid state, typically forming at or below temperatures of 0 degrees Celsius or Depending on the presence of impurities such as particles of soil or bubbles of air, it can appear transparent or a more or less opaq ...
*
KASUMI Kasumi may refer to: Places * Kasumi, Hyōgo (香住), a former town in Hyōgo Prefecture, Japan * Kasumigaseki (霞が関 "Gate of Mist"), a district in downtown Tokyo * Kasumi, Jajce, a village in Bosnia and Herzegovina Other uses * Kasumi (gi ...
*
LOKI97 In cryptography, LOKI97 is a block cipher which was a candidate in the Advanced Encryption Standard competition. It is a member of the LOKI family of ciphers, with earlier instances being LOKI89 and LOKI91. LOKI97 was designed by Lawrie Brown, ...
*
Lucifer Lucifer is one of various figures in folklore associated with the planet Venus. The entity's name was subsequently absorbed into Christianity as a name for the devil. Modern scholarship generally translates the term in the relevant Bible passage ...
*
MARS Mars is the fourth planet from the Sun and the second-smallest planet in the Solar System, only being larger than Mercury (planet), Mercury. In the English language, Mars is named for the Mars (mythology), Roman god of war. Mars is a terr ...
*
MAGENTA Magenta () is a color that is variously defined as pinkish- purplish-red, reddish-purplish-pink or mauvish-crimson. On color wheels of the RGB (additive) and CMY (subtractive) color models, it is located exactly midway between red and blue. I ...
*
MISTY1 In cryptography, MISTY1 (or MISTY-1) is a block cipher designed in 1995 by Mitsuru Matsui and others for Mitsubishi Electric. MISTY1 is one of the selected algorithms in the European NESSIE project, and has been among the cryptographic tech ...
* RC5 *
Simon Simon may refer to: People * Simon (given name), including a list of people and fictional characters with the given name Simon * Simon (surname), including a list of people with the surname Simon * Eugène Simon, French naturalist and the genus ...
*
TEA Tea is an aromatic beverage prepared by pouring hot or boiling water over cured or fresh leaves of ''Camellia sinensis'', an evergreen shrub native to East Asia which probably originated in the borderlands of southwestern China and north ...
*
Triple DES In cryptography, Triple DES (3DES or TDES), officially the Triple Data Encryption Algorithm (TDEA or Triple DEA), is a symmetric-key block cipher, which applies the DES cipher algorithm three times to each data block. The Data Encryption Standa ...
*
Twofish In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Twof ...
* XTEA Generalised Feistel: * CAST-256 * CLEFIA *
MacGuffin In fiction, a MacGuffin (sometimes McGuffin) is an object, device, or event that is necessary to the plot and the motivation of the characters, but insignificant, unimportant, or irrelevant in itself. The term was originated by Angus MacPhail for ...
*
RC2 In cryptography, RC2 (also known as ARC2) is a symmetric-key block cipher designed by Ron Rivest in 1987. "RC" stands for "Ron's Code" or "Rivest Cipher"; other ciphers designed by Rivest include RC4, RC5, and RC6. The development of RC2 wa ...
*
RC6 In cryptography, RC6 (Rivest cipher 6) is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition. ...
* Skipjack *
SMS4 ShāngMì 4 (SM4, 商密4) (formerly SMS4) is a block cipher used in the Chinese National Standard for Wireless LAN WAPI (WLAN Authentication and Privacy Infrastructure) and also used with Transport Layer Security. SM4 was a cipher proposed to ...


See also

*
Cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
*
Stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
* Substitution–permutation network *
Lifting scheme The lifting scheme is a technique for both designing wavelets and performing the discrete wavelet transform (DWT). In an implementation, it is often worthwhile to merge these steps and design the wavelet filters ''while'' performing the wavelet tr ...
for discrete wavelet transform has pretty much the same structure *
Format-preserving encryption In cryptography, format-preserving encryption (FPE), refers to encrypting in such a way that the output (the ciphertext) is in the same format as the input (the plaintext). The meaning of "format" varies. Typically only finite sets of characters ar ...
*
Lai–Massey scheme The Lai–Massey scheme is a cryptographic structure used in the design of block ciphers. It is used in IDEA and IDEA NXT. The scheme was originally introduced by Xuejia LaiX. Lai. On the design and security of block ciphers'. ETH Series in Infor ...


References

{{Cryptography navbox , block Cryptography Feistel ciphers